package test;


/**
 * @author Seon
 * @date 2023/4/8
 */
public class 拜访 {
    int startX, startY;
    int minStep = Integer.MAX_VALUE;
    int minLinesCnt = 0;
    int[][] view = new int[100][100];
    int[] dX = {0, 1, 0, -1};
    int[] dY = {1, 0, -1, 0};
    /**
     * 起点是1， 终点是2，障碍物-1，0为可通行
     * @param CityMap
     * @param n
     * @param m
     * @return
     */
    public int countPath (int[][] CityMap, int n, int m) {
        // 在CityMap中搜索目标和起点的位置。
        for (int i = 0; i < CityMap.length; i ++) {
            for (int j = 0; j < CityMap[0].length; j++) {
                if (CityMap[i][j] == 1) {
                    startX = i;
                    startY = j;
                    break;
                }
            }
        }
        Point point = new Point(startX, startY, 0);
        view[startX][startY] = 1;
        dfs(CityMap, point);
        return minLinesCnt;
    }

    public void dfs(int[][] CityMap, Point point) {
        if (CityMap[point.x][point.y] == 2) {
            if (point.step < minStep) {
                minStep = point.step;
                minLinesCnt = 1;
            } else if (point.step == minStep) {
                minLinesCnt ++;
            }
            return ;
        }
        // 如果不是终点
        for (int i = 0; i < 4; i ++) {
            int x = point.x;
            int y = point.y;
            // 四个方向依次递归探索, 方向分别为右，下， 左，上。
            int tx, ty;
            tx = x + dX[i];
            ty = y + dY[i];
            if (tx < 0 || tx > CityMap.length-1 || ty < 0 || ty > CityMap[0].length-1) {
                continue;
            }
            if (CityMap[tx][ty] == 0 && view[tx][ty] == 0) {
                view[tx][ty] = 1;
                dfs(CityMap, new Point(tx, ty, point.step+1));
                view[tx][ty] = 0;
            }
        }
        return ;
    }

    /**
     * 用这个类来进行每一个节点的存储。
     */
    class Point {
        int x, y, step;
        public Point(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
}
